package leetcode.tree.binary.path;

import leetcode.tree.binary.TreeNode;

/**
 * 112. 路径总和
 *
 * 判断该树中是否存在根节点到叶子节点的路径, 这条路径上所有节点值相加等于目标和 targetSum
 *
 */
public class HasPathSum {

    public boolean hasPathSum0(TreeNode root, int targetSum) {
        return root != null && search(root, 0, targetSum);
    }

    /**
     * 使用先序遍历 判断根节点到叶子节点的路径长度
     *
     * 自己写的 临界值的判断写的不是很好, 主要是根节点的判断
     *
     * @param root      树对象
     * @param sum       叶子节点到父亲节点的路径长度
     * @param targetSum 目标值
     * @return
     */
    public boolean search(TreeNode root, int sum, int targetSum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            sum = sum + root.val;
            return sum == targetSum;
        } else {
            sum = sum + root.val;
        }

        boolean left = search(root.left, sum, targetSum);
        if (left) {
            return true;
        }
        return search(root.right, sum, targetSum);
    }


    /**
     * 官方写法
     *
     * 方法含义: 判断从当前节点 root到叶子节点的路径, 是否存在其路径和为 sum
     *
     *
     * @param root      以root节点为根节点的子树
     * @param sum       路径之和
     * @return
     */
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        // 对左右两个子树进行遍历
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }

}
